Many-to-one communication is a common requirement of network applications such as sensor network applications, e.g. in the field of environmental monitoring or data gathering. Sensor nodes (SNs) essentially exchange information with a base station (BS) and seldom between themselves. The SNs generate periodic data samples and send them, possibly using other SNs to forward messages, to the BS for further processing.
Compared to the SNs, the BS is in general equipped with a more powerful processing unit and also more memory for programs and data. A centralized network architecture is most appropriate for such environment because it can exploit the resources available in the BS to perform complex routing functions, thus keeping the sensor nodes as simple as possible.
To be able to compute the required routing information the BS needs to know the complete topology of the network, i.e., all the SNs that are deployed and the quality of the wireless links between those nodes.
In case of a rather static network topology the BS could be manually configured with the topology information, but this method is error-prone and becomes impractical when the number of wireless SNs are large.
Most sensor networks have a distributed architecture in which the sensor nodes build up a local topology database by exchanging information with neighboring nodes. In such distributed architectures, there is no need for knowing the “global” topology.
The so-called PEDAMACS architecture [1] is a centralized sensor network architecture that requires for its operation an automatic topology discovery. The PEDAMACS's topology discovery comprises two phases: the topology learning and the topology collection phases. The BS starts the learning phase by broadcasting a coordination message which is assumed to be received by all nodes in the network. Following the coordination message the BS floods the network with a tree construction message, which is re-broadcasted by the SNs. A node uses the tree construction messages it receives from its neighbors to build its local topology information (i.e., its neighboring nodes and the quality of the links to these nodes) and to select the node (its parent node) it will use in case it wants to send a message to the BS.
After the topology learning phase, the BS starts the topology collection phase, also by broadcasting a coordination message, which is again assumed to be received by all nodes in the network. When a node receives the second coordination message, it transmits the local topology it has collected in the phase before to its parent for subsequent forwarding to the BS.
In both phases, the nodes have no coordination between each other yet and use carrier sense multiple access (CSMA) to cope with possible transmission collisions.
TSMP [2] is another centralized sensor network architecture. It is TDMA-based and reserves a time slot for a periodic neighbor discovery process. During this time slot, nodes exchange discovery messages randomly for the purpose of link probing. The results are reported by means of a periodic health report.
Chandra et al. [3] discloses an adaptive topology discovery in hybrid wireless networks wherein the network discovery procedure is close to that of PEDAMACS. Namely, the procedure consists of flooding (broadcasting) discovery messages into the network. Interestingly, the reception of the broadcasted messages is ascertained by having the sender retransmitting them until an acknowledgement is received. This solution increases the total number of transmitted messages and with it the intensity of the broadcast needs.
The following references, as cited above, are thus part of the background art for the present invention:    [1] S. C. Ergen, P. Varaija, “PEDAMACS: Power Efficient and Delay Aware Medium Access Protocol for Sensor Networks”, IEEE Trans on Mobile Computing, vol. 5, no 7, July 2006;    [2] K. Pister, L. Doherty, “TSMP: Time Synchronized Mesh Protocol”, Proc IASTED Int. Symposium Distributed Sensor Networks (DSN 2008), Nov. 16-18, 2008, Orlando, Fla., USA; and    [3] R. Chandra, C. Fetzer, K. Hogstedt; “Adaptive Topology Discovery in Hybrid Wireless Networks”; Informatics '02.